graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, Schnyder's theorem is a characterization of planar graphs in terms of the

order dimension In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller di ...

of their incidence posets. It is named after Walter Schnyder, who published its proof in

1989 File:1989 Events Collage.png, From left, clockwise: The Cypress structure collapses as a result of the 1989 Loma Prieta earthquake, killing motorists below; The proposal document for the World Wide Web is submitted; The Exxon Valdez oil tanker runs ...

. The incidence poset of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

with

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet * Vertex (computer graphics), a data structure that describes the positio ...

set and

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed ...

set is the

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...

height Height is measure of vertical distance, either vertical extent (how "tall" something or someone is) or vertical position (how "high" a point is). For example, "The height of that building is 50 m" or "The height of an airplane in-flight is ab ...

2 that has as its elements. In this partial order, there is an order relation when is a vertex, is an edge, and is one of the two endpoints of . The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order; such a set of orderings is called a ''realizer'' of the partial order. Schnyder's theorem states that a graph is planar if and only if the order dimension of is at most three.

Extensions

This theorem has been generalized by to a tight bound on the dimension of the height-three partially ordered sets formed analogously from the vertices, edges and faces of a

convex polyhedron A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

, or more generally of an embedded planar graph: in both cases, the order dimension of the poset is at most four. However, this result cannot be generalized to higher-dimensional convex polytopes, as there exist four-dimensional polytopes whose

face lattice A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

s have unbounded order dimension. Even more generally, for

abstract simplicial complex In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely c ...

es, the order dimension of the face poset of the complex is at most , where is the minimum dimension of a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

in which the complex has a geometric realization .

Other graphs

As Schnyder observes, the incidence poset of a graph ''G'' has order dimension two if and only if the graph is a path or a subgraph of a path. For, in when an incidence poset has order dimension is two, its only possible realizer consists of two total orders that (when restricted to the graph's vertices) are the reverse of each other. Any other two orders would have an intersection that includes an order relation between two vertices, which is not allowed for incidence posets. For these two orders on the vertices, an edge between consecutive vertices can be included in the ordering by placing it immediately following the later of the two edge endpoints, but no other edges can be included. If a graph can be

colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in Sout ...

with four colors, then its incidence poset has order dimension at most four . The incidence poset of a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

on ''n'' vertices has order dimension

\Theta(\log\log n)

References

*. *. *. *. *. *{{citation , last = Spencer , first = J. , authorlink = Joel Spencer , journal = Acta Mathematica Academiae Scientiarum Hungaricae , mr = 0292722 , pages = 349–353 , title = Minimal scrambling sets of simple orders , volume = 22 , year = 1971 , issue = 3–4 , doi=10.1007/bf01896428 , doi-access=free, s2cid = 123142998 . Order theory Planar graphs Theorems in graph theory